package Cache;
/**
 * 不要使用原生LinkedHashMap；自己创建双向链表+hashmap实现LRU
 * */


import java.util.concurrent.ConcurrentHashMap;

/**
 * 双向链表
 *
 * */
class DlinkNode{
    DlinkNode pre;
    DlinkNode next;
    int value;
    int key;
    public DlinkNode(){};
    public DlinkNode(int key,int value){
        this.key=key;
        this.value=value;
    }
}


public class LRUWithMap {
    ConcurrentHashMap<Integer,DlinkNode> cache;
    int capacity=0;  //HashMap容量
    DlinkNode head;  //双向链表头节点
    DlinkNode tail;  //双向链表尾节点

    public LRUWithMap() {

    }

    public LRUWithMap(int capacity) {
        cache = new ConcurrentHashMap<Integer,DlinkNode>();  //初始化
        this.capacity = capacity;  //初始化容量
        //初始化头尾结点，并进行连接
        head=new DlinkNode();
        tail=new DlinkNode();
        head.next=tail;
        tail.pre=head;
    }

    /**
     * 当用key获取元素时，如果不存在，直接返回-1
     * 存在则更新这个缓存，将其放到链表尾部
     *
     * */
    public int get(int key){
        if(!cache.containsKey(key)){
            return -1;
        }
        //获得该节点
        DlinkNode node = cache.get(key);
        //将当前节点移动到头部
        move2Head(node);
        //返回该节点值
        return node.value;
    }

    /**
     * 存入节点，并更新节点的缓存即位置，如果长度满了，需要删除尾部节点.
     * */
    public void put(int key, int val){
        //存入节点时，如果key已存在，则覆盖val并且更新缓存
        if(cache.containsKey(key)){
            //从HashMap中获取对应的结点
            DlinkNode node=cache.get(key);
            //更新该结点的值
            node.value=val;
            //将该结点移动到链头
            move2Head(node);
        }else{
            //不存在，则添加，添加时还要判断容量，容量满了需要删除尾节点
            if(cache.size()==capacity){ //容量不足
                //从HashMap中删除链尾结点
                cache.remove(tail.pre.key);
                //从链表中删除链尾结点
                delete(tail.pre);
            }
            //创建一个新的结点
            DlinkNode node=new DlinkNode(key,val);
            //添加到链头
            add2Head(node);
            //添加到HashMap中
            cache.put(key,node);
        }
    }

    /**
     * 将当前节点移动到链表头
     * */
    private void move2Head(DlinkNode node){
        delete(node);

        add2Head(node);
    }

    /**
     * 删除当前节点，更新指针
     * */
    private void delete(DlinkNode node){
        //当前节点的右节点的左节点指向当前节点的左节点
        node.next.pre = node.pre;
        //当前节点左节点的next节点指向当前节点的next
        node.pre.next = node.next;
    }

    /**
     * 在链头添加节点，更新指针
     * */
    private void add2Head(DlinkNode node){
        //head是头指针  将新结点和原头节点连起来
        head.next.pre = node;
        node.next = head.next;
        //将新节点和head连起来
        head.next = node;
        node.pre = head;
    }




}
